package pers.qianyu.month_202012.date_20201230;

/**
 * 338. 比特位计数
 * https://leetcode-cn.com/problems/counting-bits/
 *
 * @author mizzle rain
 * @date 2020-12-30 20:58
 */
public class CountBits {
    public int[] countBits(int num) {
        int[] dp = new int[num + 1];
        dp[0] = 0;
        for (int i = 1; i <= num; i++) {
            dp[i] = (i & 1) == 1 ? dp[i >> 1] + 1 : dp[i >> 1];
        }
        return dp;
    }
}
